Graph analysis is a recently popularized way of analyzing data, which considers not only properties of entities but also relationships between entities. Many algorithms for graph analysis are based on breadth-first search (BFS). BFS systematically traverses a graph from a source vertex to vertices of increasing distance away. The distance may be determined by the number of traversed edges from a respective source vertex. All vertices of a given distance from the source vertex are processed before BFS expands the distance to include vertices one edge further away. BFS repeatedly expands the distance until all vertices of a graph are reached or until a termination condition occurs.
Some graph algorithms entail running multiple BFSs from different source vertices in a graph. Examples of such algorithms include closeness centrality and betweenness centrality. Existing systems solve this problem by running all necessary BFSs independently. These systems do not leverage shared computation between the BFSs. Consequently, many graph traversals are made redundantly, which costs extra time, space, and energy.
A technique, referred to herein as multi-source BFS (MS-BFS), enables fast computation of multiple BFSs by efficiently performing several simultaneous instances of BFS traversals. Hence, the MS-BFS technique provides performance benefits. A generic MS-BFS may be implemented as an encapsulated function that an application may directly invoke from user logic. User logic may specify processing to occur on each visited node or edge and what conditions terminate each search.
However with user logic that mixes non-trivial analysis and independent BFSs, users may be challenged to retrofit the MS-BFS technique into their graph analysis, because consolidating independent BFSs can be complicated. Specifically, users may need to combine fragile analytic logic with complicated MS-BFS traversal logic, which is not straightforward. Hand coding to manage an execution context required by analytic logic during a traversal is error prone and difficult to optimize.